package cm.unit4.theme4;

import java.util.*;

public class Permutation {

    ArrayList<String> list;
    Set<String> set;
    boolean []vis;

    public ArrayList<String> Permutation(String str) {
        int k = 0;
        int len = str.length();
        list = new ArrayList<>();
        set = new TreeSet<>();
        vis = new boolean[str.length()];

        StringBuilder builder = new StringBuilder(str.length());
        Map<Character,Integer> map = new TreeMap<>();


        Character ch;

        for (int i = 0; i < str.length(); i++) {
            ch = str.charAt(i);
            if (map.get(ch)==null){
                map.put(ch,1);
            }else{
                map.put(ch,map.get(ch)+1);
            }
        }

        map.forEach((key,value)->{
            for (int i = 0; i < value; i++) {
                builder.append(key);
            }
        });

//        PermutationFunc(set,builder,0);
//        set.forEach(value->list.add(value));

        PermutationFunc(list,builder,0);

        return list;
    }

    public void PermutationFunc(Set<String> set, StringBuilder str, int k){
        if (k==str.length()){
            set.add(new String(str));
        }else {

            for (int i = k; i < str.length(); i++) {
                // 一点点优化
                if (i+1<str.length() && str.charAt(i+1)==str.charAt(i)){
                    break;
                }
                // 获取第k位的字符到ch
                char ch = str.charAt(k);
                // 用第i位字符替换第k位
                str.setCharAt(k,str.charAt(i));
                // 用ch替换第i位字符
                str.setCharAt(i,ch);

                PermutationFunc(set,new StringBuilder(str),k+1);

                ch = str.charAt(k);
                str.setCharAt(k,str.charAt(i));
                str.setCharAt(i,ch);
            }
        }
    }

    public void PermutationFunc(List<String> list, StringBuilder str, int k){
        if (k==str.length()){
            list.add(new String(str));
        }else {

            char ch;
            for (int i = k; i < str.length(); i++) {
                // 现在准备选取的元素和上一个元素相同，但是上一个元素还没被使用
//                if (i+1<str.length() && str.charAt(i)==str.charAt(i+1)&&!vis[i]){
//                    continue;
//                }
                if (!vis[i]){
                    vis[i] = true;
                    // 获取第k位的字符到ch
                    ch = str.charAt(k);
                    // 用第i位字符替换第k位
                    str.setCharAt(k,str.charAt(i));
                    // 用ch替换第i位字符
                    str.setCharAt(i,ch);

                    PermutationFunc(list,new StringBuilder(str),k+1);

                    ch = str.charAt(k);
                    str.setCharAt(k,str.charAt(i));
                    str.setCharAt(i,ch);
                    vis[i] = false;
                }
            }
        }
    }


    public static void main(String[] args){
        Permutation permutation = new Permutation();
        System.out.println(permutation.Permutation("abc"));
        System.out.println(permutation.Permutation("aaa"));
        System.out.println(permutation.Permutation("aabc"));
    }
}
